package 每日一题;

import java.util.ArrayDeque;
import java.util.Deque;

public class No84柱状图中最大的矩形 {

    /**
     * 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
     * 求在该柱状图中，能够勾勒出来的矩形的最大面积。
     * 以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。
     * 图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。
     *
     * 示例:
     * 输入: [2,1,5,6,2,3]
     * 输出: 10
     */

    public int largestRectangleArea(int[] heights) {

        /**
         * 1.每列向两边扩散,找到两边比当前矮的左边 left right
         * 2.单调栈
         */
        return method1(heights);
    }

    //利用单调栈
    private int method1(int[] heights) {

        //栈中存放下标,栈中就是边界
        Deque<Integer> stack=new ArrayDeque<>();
        stack.addLast(-1);
        int maxArea=0;
        int index=0;

        // 1 5 6 2 3 4
        //栈中必须是递增的
        while (index<heights.length){

            int currentHeight=0;
            //因为栈中是递增的,所以一个if就够了   需要等于,因为两个相等的在一起,那么记录一个就够了
            while (stack.peekLast()!=-1&&heights[stack.peekLast()]>=heights[index]){
                //栈顶不为空并且栈顶元素大于当前元素,那么栈顶元素的右边界就是当前元素
                currentHeight=heights[stack.pollLast()];
                //现在栈顶就是左边界
                int left=stack.peekLast();
                int length=index-left-1;
                int area=currentHeight*length;
                maxArea=Math.max(maxArea,area);
            }
            stack.addLast(index);
            index++;
        }

        //如果栈中还有
        int right=heights.length-1;
        while (stack.peekLast()!=-1){

            Integer height = heights[stack.pollLast()];

            int left=stack.peekLast();

            int length=right-left;

            int area=height*length;

            maxArea=Math.max(maxArea,area);
        }

        return maxArea;
    }


    //求当前柱子两边的边界 n^2 复杂度 超时
    private int method2(int[] heights){

        int maxArea=0;

        for (int i = 0; i < heights.length; i++) {

            int left=1;
            //求左边第一个比当前柱子矮(或等于)的
            for (int j = i-1; j >= 0; j--) {
                if(heights[j]>=heights[i]){
                    left--;
                }else{
                    break;
                }
            }
            int right=1;
            //求右边第一个比当前柱子矮(或等于)的
            for (int j = i+1; j < heights.length; j++) {
                if(heights[j]>=heights[i]){
                    right++;
                }else{
                    break;
                }
            }
            int width=right-left+1;
            maxArea=Math.max(maxArea,width*heights[i]);
        }

        return maxArea;
    }

    public static void main(String[] args) {
        No84柱状图中最大的矩形 n=new No84柱状图中最大的矩形();
        int[] arr=new int[]{2, 1, 5, 6, 2, 3};
        int result1 = n.method1(arr);
        int result2 = n.method2(arr);
        System.out.println(result1);
        System.out.println(result2);
    }

}
